﻿#define _CRT_SECURE_NO_WARNINGS 1
//平面内有n个矩形, 第i个矩形的左下角坐标为(x1[i], y1[i]), 右上角坐标为(x2[i], y2[i])。
//如果两个或者多个矩形有公共区域则认为它们是相互重叠的(不考虑边界和角落)。
//请你计算出平面内重叠矩形数量最多的地方, 有多少个矩形相互重叠。
//#include <stdio.h>
//int main()
//{
//	int x[50][2];
//	int y[50][2];
//	int tmp = 0;
//	int i = 0;
//	int j = 0;
//	int k = 0;
//	int max = 0;
//	int n = 0;
//	scanf("%d", &n);
//	for (i = 0; i<n; i++)
//	{
//		scanf("%d", &x[i][0]);
//	}
//	for (i = 0; i<n; i++)
//	{
//		scanf("%d", &y[i][0]);
//	}
//	for (i = 0; i<n; i++)
//	{
//		scanf("%d", &x[i][1]);
//	}
//	for (i = 0; i<n; i++)
//	{
//		scanf("%d", &y[i][1]);
//	}
//	for (j = 0; j<n; j++)
//	{
//		for (k = 0; k<n; k++)
//		{
//			tmp = 0;
//			for (i = 0; i<n; i++)
//			{
//				if (x[j][0] >= x[i][0] && x[j][0]<x[i][1])
//				{
//					if (y[k][0] >= y[i][0] && y[k][0]<y[i][1])
//					{
//						tmp++;
//					}
//				}
//			}
//			if (max<tmp)
//			{
//				max = tmp;
//			}
//		}
//	}
//	printf("%d", max);
//	return 0;
//}
//
//
//
//
//
//
//
//牛牛和妞妞去海边捡了一大袋美丽的贝壳，千辛万苦地运回家后，牛牛和妞妞打算分掉这些贝壳。
//牛牛提出，他和妞妞轮流从还没有分配的贝壳中取一定数量的贝壳，直到贝壳分完为止。分配规则是牛牛每次取剩余贝壳的1 / 10（向下取整），妞妞每次固定取m个贝壳，妞妞先取。
//妞妞想要得到不少于一半的贝壳，又不想太过分，那么她一次最少取多少个贝壳才能得到不少于一半的贝壳呢
//#include <stdio.h>
//int func(long n, long m)
//{
//	long res = n;
//	long boy = 0, time = 0;
//	while (1)
//	{
//		time++;
//		res -= m;
//		if (time*m>n / 2)
//		{
//			return 1;
//		}
//		else
//		{
//			long tmp = res / 10;
//			boy += tmp;
//			res -= tmp;
//			if (boy>n / 2)
//			{
//				return 0;
//			}
//		}
//	}
//}
//int main()
//{
//	long num = 0;
//	while (~scanf("%ld", &num))
//	{
//		long low = 1;
//		long high = num;
//		long mid = (low + high) / 2;
//		while (1)
//		{
//			if (func(num, mid) == 1)
//			{
//				if (func(num, mid - 1) == 0)
//				{
//					printf("%ld\n", mid);
//					break;
//				}
//				high = mid;
//				mid = (low + high) / 2;
//			}
//			else if (func(num, mid) == 0)
//			{
//				if (func(num, mid + 1) == 1)
//				{
//					printf("%ld", mid + 1);
//					break;
//				}
//				low = mid;
//				mid = (high + low) / 2;
//			}
//		}
//	}
//	return 0;
//}
//
//
//
//
//
//
//
//
//
//一个数组有 N 个元素，求连续子数组的最大和。 例如：[-1, 2, 1]，和最大的连续子数组为[2, 1]，其和为 3
//#include <stdio.h>
//#include <string.h>
//#include <stdlib.h>
//int main()
//{
//	int num = 0;
//	scanf("%d", &num);
//	int *r = { 0 };
//	r = (int *)malloc(num*sizeof(int));
//	for (int j = 0; j<num; j++)
//	{
//		scanf("%d", &r[j]);
//	}
//	int max = 0;
//	int sum = 0;
//	int flag = 0;
//	for (int l = 0; l<num; l++)
//	{
//		if (r[l]<0)
//		{
//			flag++;
//		}
//	}
//	int max1 = r[0];
//	if (flag == num)
//	{
//		for (int p = 0; p<num; p++)
//		{
//			if (r[p]>max1)
//			{
//				max1 = r[p];
//			}
//		}
//		printf("%d", max1);
//	}
//	else
//	{
//		for (int k = 0; k<num; k++)
//		{
//			sum += r[k];
//			if (sum>max)
//			{
//				max = sum;
//			}
//			if (sum<0)
//			{
//				sum = 0;
//			}
//		}
//		printf("%d", max);
//	}
//	return 0;
//}
//
//
//
//
//
//
//
//
//在商城的某个位置有一个商品列表，该列表是由L1、L2两个子列表拼接而成。当用户浏览并翻页时，需要从列表L1、L2中获取商品进行展示。展示规则如下：
//1. 用户可以进行多次翻页，用offset表示用户在之前页面已经浏览的商品数量，比如offset为4，表示用户已经看了4个商品
//2. n表示当前页面需要展示的商品数量
//3. 展示商品时首先使用列表L1，如果列表L1长度不够，再从列表L2中选取商品
//4. 从列表L2中补全商品时，也可能存在数量不足的情况
//请根据上述规则，计算列表L1和L2中哪些商品在当前页面被展示了
//#include <stdio.h>
//int main()
//{
//	int off, n, len1, len2;
//	scanf("%d%d%d%d", &off, &n, &len1, &len2);
//	int str1 = 0, end1 = 0, str2 = 0, end2 = 0;
//	if (off<len1)
//	{
//		if (off + n<len1)
//		{
//			str1 = off;
//			end1 = n + 1;
//		}
//		else
//		{
//			str1 = off;
//			end1 = len1;
//			end2 = off + n - len1;
//		}
//		if (n == 0)
//		{
//			end1 = str1;
//		}
//	}
//	else
//	{
//		str1 = len1;
//		end1 = len1;
//		str2 = off - len1>len2 ? len2 : off - len1;
//		end2 = str2 + n>len2 ? len2 : str2 + n;
//	}
//	printf("%d %d %d %d", str1, end1, str2, end2);
//	return 0;
//}
//
//
//
//
//
//
//某种特殊的数列a1, a2, a3, ...的定义如下：a1 = 1, a2 = 2, ..., an = 2 * an − 1 + an - 2 (n > 2)。
//给出任意一个正整数k，求该数列的第k项模以32767的结果是多少？#include <stdio.h>
//int main()
//{
//	int n = 0;
//	int i = 0;
//	while (scanf("%d", &n) != EOF)
//	{
//		int arr[n];
//		int max = 0;
//		for (i = 0; i<n; i++)
//		{
//			scanf("%d", &arr[i]);
//			max = max>arr[i] ? max : arr[i];
//		}
//		int num[max];
//		num[0] = 1;
//		num[1] = 2;
//		for (i = 2; i<max; i++)
//		{
//			num[i] = (2 * num[i - 1] + num[i - 2]) % 32767;
//		}
//		for (i = 0; i<n; i++)
//		{
//			printf("%d\n", num[arr[i] - 1]);
//		}
//	}
//	return 0;
//}
//
//
//
//
//
//有一个数组a[N]顺序存放0~N - 1，要求每隔两个数删掉一个数，到末尾时循环至开头继续进行，求最后一个被删掉的数的原始下标位置。
//以8个数(N = 7)为例:｛0，1，2，3，4，5，6，7｝，0->1->2(删除)->3->4->5(删除)->6->7->0(删除), 如此循环直到最后一个数被删除。
//#include <stdio.h>
//#include <malloc.h>
//int del(int *inp, int *out, int len, int yu)
//{
//	int i = 0;
//	int cnt = 0;
//	for (i = 0; i<len; i++)
//	{
//		if ((i + yu) % 3 == 2)
//		{
//
//		}
//		else
//		{
//			out[cnt] = inp[i];
//			cnt++;
//		}
//	}
//	yu = (len + yu) % 3;
//	if (cnt == 1)
//	{
//		return out[0];
//	}
//	else
//	{
//		return del(out, inp, cnt, yu);
//	}
//}
//int main()
//{
//	int num = 0;
//	int i = 0;
//	int res = 0;
//	while (~scanf("%d", &num))
//	{
//		if (num >= 1000)
//		{
//			num = 999;
//		}
//		int out[1000];
//		int inp[1000];
//		for (i = 0; i<1000; i++)
//		{
//			inp[i] = i;
//		}
//		res = del(inp, out, num, 0);
//		printf("%d\n", res);
//	}
//	return 0;
//}
//
//
//
//
//
//
//小易经常沉迷于网络游戏.有一次, 他在玩一个打怪升级的游戏, 
//他的角色的初始能力值为 a.在接下来的一段时间内, 他将会依次遇见n个怪物, 
//每个怪物的防御力为b1, b2, b3...bn.如果遇到的怪物防御力bi小于等于小易的当前能力值c, 
//那么他就能轻松打败怪物, 并 且使得自己的能力值增加bi; 如果bi大于c, 那他也能打败怪物, 
//但他的能力值只能增加bi
//与c的最大公约数.那么问题来了, 在一系列的锻炼后, 小易的最终能力值为多少 ?
//#include <stdio.h>
//int max(int m, int n)
//{
//	int s = 0;
//	if (m>n)
//	{
//		s = n;
//	}
//	else
//	{
//		s = m;
//	}
//	while (s>0)
//	{
//		if (m%s == 0 && n%s == 0)
//		{
//			break;
//		}
//		else
//		{
//			s--;
//		}
//	}
//	return s;
//}
//int main()
//{
//	int a = 0;
//	int n = 0;
//	while (scanf("%d %d", &n, &a) != EOF)
//	{
//		int b[n];
//		int i = 0;
//		for (i = 0; i<n; i++)
//		{
//			scanf("%d", &b[i]);
//			if (b[i] <= a)
//			{
//				a += b[i];
//			}
//			else
//			{
//				a = a + max(a, b[i]);
//			}
//		}
//		printf("%d\n", a);
//	}
//	return 0;
//}
//
//
//
//
//
//
//
//小青蛙有一天不小心落入了一个地下迷宫, 小青蛙希望用自己仅剩的体力值P跳出这个地下迷宫。为了让问题简单, 
//假设这是一个n*m的格子迷宫, 迷宫每个位置为0或者1, 0代表这个位置有障碍物, 小青蛙达到不了这个位置; 1代表小青蛙可以达到的位置。
//小青蛙初始在(0, 0)位置, 地下迷宫的出口在(0, m - 1)(保证这两个位置都是1, 并且保证一定有起点到终点可达的路径), 
//小青蛙在迷宫中水平移动一个单位距离需要消耗1点体力值, 向上爬一个单位距离需要消耗3个单位的体力值, 向下移动不消耗体力值, 
//当小青蛙的体力值等于0的时候还没有到达出口, 
//小青蛙将无法逃离迷宫。现在需要你帮助小青蛙计算出能否用仅剩的体力值跳出迷宫(即达到(0, m - 1)位置)。
//#include <stdio.h>
//
//#define MAX 11
//
//typedef struct _node{
//	int point_x;
//	int point_y;
//	int hp;
//}node;
//
//int n, m, p;
//int point[MAX][MAX], point_visited[MAX][MAX], top = -1, x, y;
//node route[MAX * MAX];
//
//int judge(int i, int j)
//{
//
//	if ((j + 1 <= m) && (point[i][j + 1] == 1) && (p - 1 >= 0) && (point_visited[i][j + 1] == 0))
//	{
//		p -= 1;
//		return 4;
//	}
//	else  if ((i - 1 >= 0) && (point[i - 1][j] == 1) && (p - 3 >= 0) && (point_visited[i - 1][j] == 0))
//	{
//		p -= 3;
//		return 1;
//	}
//	else  if ((i + 1 <= n) && (point[i + 1][j] == 1) && (point_visited[i + 1][j] == 0))
//	{
//		return 2;
//	}
//	else  if ((j - 1 >= 0) && (point[i][j - 1] == 1) && (p - 1 >= 0) && (point_visited[i][j - 1] == 0))
//	{
//		p -= 1;
//		return 3;
//	}
//	else
//	{
//		return 0;
//	}
//}
//
//void pop()
//{
//	int i, j;
//
//	i = route[top].point_x;
//	j = route[top].point_y;
//	p = route[top].hp;
//	top--;
//
//	return;
//}
//
//void push(int i, int j)
//{
//	top++;
//	route[top].point_x = i;
//	route[top].point_y = j;
//	route[top].hp = p;
//	point[i][j] = 0;
//
//	return;
//}
//
//int main(int argc, char *argv[])
//{
//	int i, j;
//
//	scanf("%d", &n);
//	scanf("%d", &m);
//	scanf("%d", &p);
//	for (i = 0; i < n; i++)
//	{
//		for (j = 0; j < m; j++)
//		{
//			scanf("%d", &point[i][j]);
//		}
//	}
//
//	if (p < m)
//	{
//		printf("Can not escape!\n");
//		return 0;
//	}
//
//	push(x, y);
//	while (top >= 0)
//	{
//		i = judge(route[top].point_x, route[top].point_y);
//		if (i == 0)
//		{
//			pop();
//			x = route[top].point_x;
//			y = route[top].point_y;
//		}
//		else if (i == 1)//up
//		{
//			push(--x, y);
//		}
//		else if (i == 2)//down
//		{
//			push(++x, y);
//		}
//		else if (i == 3)//left
//		{
//			push(x, --y);
//		}
//		else if (i == 4)//right
//		{
//			push(x, ++y);
//		}
//
//		if ((x == 0) && (y == m - 1))
//		{
//			for (i = 0; i <= top; i++)
//			{
//				if (i == 0)
//				{
//					printf("[%d,%d]", route[i].point_x, route[i].point_y);
//				}
//				else
//				{
//					printf(",[%d,%d]", route[i].point_x, route[i].point_y);
//				}
//			}
//			return 0;
//		}
//	}
//	printf("Can not escape!\n");
//
//	return 0;
//}
//
//
//
//
//
//
//
//
//找出n个数里最小的k个
//#include <stdio.h>
//int main()
//{
//	int n = 0;
//	int k = 0;
//	int i = 0;
//	int j = 0;
//	int a[101];
//	while (scanf("%d", a + i) != EOF)
//	{
//		i++;
//	}
//	int len = i - 1;
//	k = a[i - 1];
//	int tmp = 0;
//	for (i = 0; i<len; i++)
//	{
//		for (j = i + 1; j<len; j++)
//		{
//			if (a[i]>a[j])
//			{
//				tmp = a[i];
//				a[i] = a[j];
//				a[j] = tmp;
//			}
//		}
//	}
//	for (i = 0; i<k; i++)
//	{
//		if (i<k - 1)
//		{
//			printf("%d ", a[i]);
//		}
//		else
//		{
//			printf("%d", a[i]);
//		}
//	}
//	return 0;
//}
//
//
//
//
//
//
//给定一个字符串，输出所有指定长度为n的子串，没有则输出 - 1
//#include <stdio.h>
//#include <string.h>
//
//int main()
//{
//	char arr[1000];
//	scanf("%s", &arr);
//	int n = 0;
//	scanf("%d", &n);
//	int i = 0;
//	int j = 0;
//	int len = strlen(arr);
//	if (n>len || n <= 0)
//	{
//		printf("-1");
//		return 0;
//	}
//	for (i = 0; i<len - n + 1; i++)
//	{
//		for (j = i; j<n + i; j++)
//		{
//			printf("%c", arr[j]);
//		}
//		printf(" ");
//	}
//	return 0;
//}
//
//
//
//
//
//
//#include <stdio.h>
//#include <assert.h>
//void my_strcpy(char *p, const char *num)
//{
//	assert(p != NULL);
//	assert(num != NULL);
//	while (*p++ = *num++);
//	{}
//}
//int main()
//{
//	char arr1[10] = "**********";
//	char arr2[10] = "hello bit";
//	my_strcpy(arr1, arr2);
//	printf("%s", arr1);
//	return 0;
//}





//#include <stdio.h>
//#include <assert.h>
//int my_strlen(const char* p)
//{
//	assert(p != NULL);
//	int count = 0;
//	while (*p++ != '\0')
//	{
//		count++;
//	}
//	return count;
//}
//int main()
//{
//	char arr[] = "hello bit";
//	int len = my_strlen(arr);
//	printf("arr长度为：%d", len);
//	return 0;
//}